GPU 친화적 데이터 구조 -해시 테이블과 메모리 접근 최적화

GPU 친화적 데이터 구조 -해시 테이블과 메모리 접근 최적화

로봇이 미지의 환경을 탐사하며 실시간으로 고해상도 3D 지도를 작성하는 과정은 근본적으로 ’대규모 데이터 처리’와 ’메모리 관리’의 싸움이다. 초당 수십 프레임으로 쏟아지는 RGB-D 카메라나 LiDAR의 포인트 클라우드 데이터를 처리하여, 3차원 공간의 점유 여부와 표면 거리(Distance Field)를 갱신하는 작업은 엄청난 계산 대역폭을 요구한다. 과거 Voxblox나 OctoMap과 같은 CPU 기반 매핑 프레임워크는 이러한 연산을 처리함에 있어 ’공간적 희소성(Sparsity)’을 다루기 위해 트리(Tree)나 포인터 체이싱 기반의 자료 구조를 채택했다. 그러나 현대적 로보틱스가 요구하는 밀집(Dense) 매핑과 실시간 처리에 있어, 이러한 전통적 자료 구조는 GPU 가속의 잠재력을 갉아먹는 주범이 되었다.

NvBlox가 제시하는 기술적 패러다임의 핵심은 계산의 중심을 CPU에서 GPU로 완전히 이관하는 것이며, 이를 달성하기 위해 가장 먼저 해체하고 재설계한 것이 바로 데이터를 저장하고 접근하는 ’자료 구조(Data Structure)’다. 본 절에서는 NvBlox가 어떻게 CPU 중심의 전통적 자료 구조가 가진 병목을 극복하고, NVIDIA GPU의 대규모 병렬 아키텍처(Massively Parallel Architecture)에 최적화된 형태인 **GPU 해시 테이블(GPU Hash Table)**과 블록 기반 메모리 관리 기법을 구현했는지, 그 기술적 심연을 상세히 분석한다.

1. GPU 컴퓨팅과 전통적 자료 구조의 불일치성 (Impedance Mismatch)

NvBlox의 데이터 구조를 이해하기 위해서는 먼저 왜 기존의 방식이 GPU에서 실패하는지를 명확히 인지해야 한다. Voxblox나 OctoMap과 같은 기존 시스템은 주로 옥트리(Octree) 또는 **포인터 기반의 해시 맵(Chaining Hash Map)**을 사용한다.1

1.1 옥트리(Octree)의 GPU 비효율성

옥트리는 공간을 재귀적으로 8개의 자식 노드로 분할하며 데이터를 저장한다. 이는 데이터가 없는 빈 공간에 대해 메모리를 할당하지 않으므로 CPU 환경에서는 메모리 효율적이다. 그러나 GPU의 SIMT(Single Instruction, Multiple Threads) 실행 모델에서 옥트리 순회는 치명적인 성능 저하를 유발한다.

  • 포인터 체이싱(Pointer Chasing)과 메모리 지연: 트리를 탐색하려면 루트 노드에서 리프 노드(Leaf Node)까지 포인터를 따라 이동해야 한다. 각 이동마다 글로벌 메모리의 임의 위치를 참조하게 되는데, 이는 메모리 접근 패턴을 비연속적으로 만든다. GPU는 수백 사이클의 메모리 지연(Latency)을 수천 개의 스레드를 교체하며 숨기도록 설계되었지만, 모든 스레드가 동시에 각기 다른 메모리 주소를 기다리는 상황(Memory Stall)에서는 성능이 급격히 떨어진다.
  • 워프 발산(Warp Divergence): GPU는 32개의 스레드를 묶어 하나의 워프(Warp)로 실행한다. 옥트리 탐색 과정에서 어떤 스레드는 트리의 왼쪽 자식으로, 어떤 스레드는 오른쪽 자식으로 분기해야 하는 상황이 발생하면, GPU는 이 분기들을 직렬화(Serialize)하여 순차적으로 실행해야 한다. 이는 병렬 처리 효율을 1/32 수준으로 떨어뜨릴 수 있는 심각한 문제다.3

1.2 연결 리스트(Linked List) 기반 해싱의 한계

C++ STL의 std::unordered_map으로 대표되는 전통적 해시 테이블은 충돌 발생 시 연결 리스트를 사용하는 체이닝(Chaining) 기법을 쓴다. GPU에서 동적 메모리 할당(malloc/new)을 수행하거나 연결 리스트를 순회하는 것은 스레드 간의 극심한 경쟁 상태(Race Condition)를 유발하고, 메모리 파편화(Fragmentation)를 초래하여 사실상 실시간 어플리케이션에서는 사용이 불가능하다.

2. NvBlox의 해법: 개방 주소법 기반의 GPU 해시 테이블

NvBlox는 이러한 문제를 해결하기 위해 **희소 복셀 그리드(Sparse Voxel Grid)**를 관리하는 수단으로, 포인터와 트리 탐색을 완전히 배제하고 수학적 해싱(Hashing)에 기반한 개방 주소법(Open Addressing) 해시 테이블을 GPU 상에 구현하였다.4 이는 stdgpu 라이브러리의 설계 철학을 계승 및 발전시킨 것으로, 대규모 병렬 환경에서도 O(1)의 접근 속도를 보장하며, 메모리 접근 패턴을 선형화하여 캐시 적중률을 극대화한다.4

특성옥트리 (OctoMap/CPU)체이닝 해시 (STL/CPU)NvBlox 개방 주소법 해시 (GPU)
메모리 접근포인터 체이싱 (무작위)포인터 체이싱 (무작위)선형 조사 (연속적/Coalesced)
분기(Branching)높음 (트리 깊이만큼)중간 (리스트 길이만큼)낮음 (평탄화된 코드)
병렬성낮음 (락/동기화 필요)낮음매우 높음 (Lock-free/Atomic)
캐시 효율낮음낮음높음 (공간적 지역성 활용)

2.1 데이터 구조의 2계층 계층 (Two-Level Hierarchy)

NvBlox의 맵 저장소는 효율적인 희소성 관리를 위해 2단계 계층 구조로 설계되어 있다.5

  1. Level 1: 해시 테이블 (The Indexer)
  • 3차원 공간의 좌표 (x, y, z)를 키(Key)로 받아, 해당 공간을 담당하는 **복셀 블록(VoxelBlock)**의 메모리 포인터(또는 인덱스)를 반환한다.
  • 이 테이블은 GPU 글로벌 메모리에 단일한 거대 배열로 존재하며, 수백만 개의 쿼리를 병렬로 처리한다.
  1. Level 2: 복셀 블록 (VoxelBlock)
  • 실제 물리적 데이터를 담고 있는 컨테이너다.
  • 하나의 블록은 8 \times 8 \times 8, 즉 512개의 복셀(Voxel)을 포함한다.
  • 이 구조는 TSDF 값, 가중치(Weight), 색상(Color) 등의 데이터를 구조체 배열(SoA) 형태로 저장한다.

이 구조에서 가장 중요한 기술적 도전은 “수백만 개의 센서 레이(Ray)가 동시에 맵을 업데이트하려 할 때, 어떻게 충돌 없이 빠르게 해당 복셀 블록을 찾거나 생성할 것인가?“이다.

2.2 선형 조사법(Linear Probing)과 캐시 지역성

NvBlox는 해시 충돌(Hash Collision)을 해결하기 위해 **선형 조사법(Linear Probing)**을 채택했다.9 이는 해시 함수 h(k)가 가리키는 슬롯이 이미 점유되어 있다면, 인덱스를 1씩 증가시키며 (h(k)+1, h(k)+2, \dots) 바로 옆 칸을 순차적으로 확인하는 방식이다.

일견 단순해 보이는 이 방식이 GPU에서는 복잡한 뻐꾸기 해싱(Cuckoo Hashing)이나 이중 해싱(Double Hashing)보다 훨씬 강력한 성능을 발휘한다. 그 이유는 메모리 버스트(Memory Burst)와 캐시 라인(Cache Line) 때문이다.

  • 메모리 응집(Coalescing): GPU가 글로벌 메모리에서 데이터를 읽어올 때는 최소 32바이트 또는 128바이트(L2 캐시 라인 크기) 단위의 트랜잭션이 발생한다.
  • 캐시 히트(Cache Hit): 선형 조사법을 사용하면, 충돌이 발생해 다음 슬롯을 확인할 때 해당 데이터가 이미 이전 트랜잭션에 의해 L2 캐시나 L1 캐시에 로드되어 있을 확률이 매우 높다. 반면, 2차 조사법이나 이중 해싱은 충돌 시 메모리의 먼 곳으로 점프하므로 매번 새로운 메모리 트랜잭션(Cache Miss)을 유발하여 대기 시간(Latency)을 증가시킨다.11

2.3 공간 해싱(Spatial Hashing) 함수

3차원 정수 좌표 \mathbf{x} = (x, y, z)를 1차원 해시 테이블 인덱스로 변환하기 위해 NvBlox는 공간 해싱(Spatial Hashing) 기법을 사용한다. 일반적으로 큰 소수(Prime Number)를 사용하는 다음과 같은 형태의 해시 함수가 활용된다.13
hash(x, y, z) = ((x \cdot p_1) \oplus (y \cdot p_2) \oplus (z \cdot p_3)) \mod N
여기서 p_1, p_2, p_3는 매우 큰 소수이며, N은 해시 테이블의 크기이다. \oplus는 XOR 연산을 의미한다. 이 함수는 인접한 3D 좌표들이 해시 테이블 상에서 서로 멀리 떨어지도록(Scattering) 유도하여 클러스터링을 방지하지만, NvBlox는 선형 조사법과의 시너지를 위해 적절한 지역성 또한 고려한다.

3. 병렬성 제어와 원자적 연산 (Concurrency & Atomics)

수만 개의 스레드가 동시에 맵을 업데이트할 때, 동일한 위치에 새로운 VoxelBlock을 생성해야 하는 상황이 빈번하게 발생한다. 이를 **경쟁 상태(Race Condition)**라 하며, 적절한 동기화 없이는 데이터 무결성이 깨진다.

3.1 락-프리(Lock-Free) 삽입 알고리즘

NvBlox는 락(Lock)을 걸어 스레드를 대기시키는 방식 대신, CUDA 하드웨어가 지원하는 **원자적 연산(Atomic Operation)**을 활용하여 논블로킹(Non-blocking) 방식으로 이를 해결한다.10

NvBlox의 해시 테이블 삽입 및 조회 로직은 다음과 같이 작동한다:

  1. 해시 키 생성: 3차원 인덱스로부터 키를 생성한다.
  2. 슬롯 조회: 해당 슬롯이 비어있는지 확인한다.
  3. 원자적 비교 및 교환 (Atomic CAS): 비어있다면 atomicCAS(address, compare, val) 명령어를 통해 자신의 키를 기록하려 시도한다.
  • 이 명령어는 하드웨어 레벨에서 단 하나의 스레드만 성공함을 보장한다.
  • 성공한 스레드는 새로운 VoxelBlock을 할당하고 포인터를 연결한다.
  • 실패한 스레드(다른 스레드가 간발의 차로 먼저 쓴 경우)는 다음 슬롯으로 이동(선형 조사)하거나, 이미 생성된 블록을 사용한다.

이러한 방식은 수천 개의 스레드가 락 대기로 인해 멈추는 현상(Convoy Effect)을 방지하며, GPU의 가동률(Occupancy)을 최대로 유지하게 한다.

3.2 부하율(Load Factor) 관리와 리사이징

개방 주소법의 단점은 테이블이 가득 찰수록 충돌 빈도가 기하급수적으로 늘어나 성능이 급락한다는 점이다. NvBlox는 해시 테이블의 **부하율(Load Factor)**을 모니터링하며, 통상적으로 0.5~0.7(50%~70%)을 넘어가면 테이블의 크기를 2배로 늘리는 리사이징(Resizing)을 수행한다.14

리사이징은 기존 데이터를 새로운 테이블로 모두 옮겨야 하는(Rehashing) 비용이 큰 작업이므로, NvBlox는 초기화 시 충분한 크기를 할당하거나, 시스템 유휴 시간에 점진적으로 수행하는 전략을 통해 실시간성을 해치지 않도록 설계되어 있다. 로그에서 관찰되는 Resizing GPU hash capacity from 4096 to 8192 메시지는 이러한 동적 관리 시스템이 작동하고 있음을 보여준다.

4. 메모리 레이아웃 최적화: SoA vs AoS

데이터 구조의 논리적 설계만큼이나 중요한 것이 물리적 메모리 배치(Layout)다. NvBlox는 **구조체 배열(AoS: Array of Structures)**과 배열의 구조체(SoA: Structure of Arrays) 사이의 트레이드오프를 GPU 아키텍처 관점에서 최적화했다.6

4.1 AoS (Array of Structures)의 문제점

전통적인 객체 지향 방식(AoS)은 복셀 하나를 객체로 보고 데이터를 묶는다.

// AoS 방식 (비효율적)
struct Voxel {
float distance; // 4 bytes
float weight;   // 4 bytes
uchar3 color;   // 3 bytes
//... padding...
};
Voxel grid[N];

이 구조에서 워프 내 32개 스레드가 동시에 distance 값만 읽어서 업데이트하려 할 때 문제가 발생한다. 메모리 상에서 distance 값들은 sizeof(Voxel)만큼 띄엄띄엄 배치되어 있다(Strided Access). GPU 메모리 컨트롤러는 불필요한 데이터(color 등)까지 포함된 여러 개의 캐시 라인을 읽어와야 하므로 유효 대역폭(Effective Bandwidth)이 낭비된다.

4.2 NvBlox의 선택: SoA (Structure of Arrays)

NvBlox는 VoxelBlock 내부에서 데이터를 속성별로 분리하여 저장하는 SoA 방식을 채택하거나, 적어도 블록 단위의 연속성을 보장한다.6

// NvBlox 스타일 VoxelBlock (GPU 최적화)
struct VoxelBlock {
float distances; // 8x8x8 연속 메모리
float weights;   // 8x8x8 연속 메모리
uchar3 colors;   //...
};

이 구조에서는 인접한 스레드들이 인접한 메모리 주소(distances[i], distances[i+1]...)에 접근하게 된다. 이는 메모리 응집(Memory Coalescing) 조건을 완벽하게 충족시켜, 단 한 번의 메모리 트랜잭션으로 워프 전체의 데이터를 로드할 수 있게 한다. NvBlox가 Voxblox 대비 표면 통합 속도에서 177배의 성능 향상을 이룰 수 있었던 핵심적인 이유 중 하나가 바로 이 메모리 레이아웃 변경을 통한 대역폭 효율화이다.5

4.3 8x8x8 블록 크기의 수학적 근거

NvBlox가 512개(8 \times 8 \times 8)의 복셀을 하나의 블록으로 묶는 것에는 하드웨어적 이유가 있다.7

  1. 메모리 정렬(Alignment): 512개의 float(4바이트) 데이터는 2KB이다. 이는 GPU의 메모리 페이지 크기 및 캐시 라인 크기와 정렬하기 용이하다.
  2. 표면적 대 부피 비 최적화: 블록이 너무 작으면 해시 테이블의 관리 오버헤드가 커지고, 너무 크면 빈 공간(Air)까지 메모리를 할당해야 하는 낭비가 발생한다. 8이라는 수치는 3차원 공간에서 표면을 표현할 때 메모리 효율과 관리 오버헤드 사이의 균형점(Sweet Spot)으로 실험적으로 검증된 수치다.

5. 통합 메모리(Unified Memory)와 스트리밍

NvBlox는 엔비디아의 통합 메모리(Unified Memory, Managed Memory) 기술을 적극적으로 활용하여 호스트(CPU)와 디바이스(GPU) 간의 유연한 데이터 공유를 지원한다.17

5.1 cudaMallocManaged와 제로 카피

Jetson AGX Orin과 같은 임베디드 플랫폼에서는 CPU와 GPU가 물리적 메모리(DRAM)를 공유한다. NvBlox는 cudaMallocManaged를 사용하여 할당된 메모리를 통해, 명시적인 cudaMemcpy 없이도 포인터 하나로 CPU와 GPU 양쪽에서 데이터에 접근할 수 있게 한다.

  • 맵 직렬화(Serialization): 맵을 디스크에 저장하거나 네트워크로 전송할 때, 별도의 GPU->CPU 복사 코드 없이 해당 메모리 영역을 바로 읽어 처리한다.
  • 동적 페이징(Page Migration): 필요에 따라 드라이버가 페이지 단위로 데이터를 GPU 캐시나 호스트 메모리로 이동시킨다.

다만, 무분별한 통합 메모리 사용은 페이지 폴트(Page Fault) 오버헤드를 유발할 수 있다. 따라서 NvBlox는 빈번하게 접근되는 활성(Active) 블록이나 인덱스 테이블에 대해서는 커스텀 할당자(Allocator)를 통해 GPU 전용 메모리(Device Memory)에 고정(Pinning)하거나 cudaMemPrefetchAsync를 사용하여 미리 데이터를 GPU로 가져오는 최적화 기법을 적용한다.

6. 결론: 하드웨어를 이해하는 데이터 구조의 승리

NvBlox의 데이터 구조는 단순히 3차원 좌표를 저장하는 그릇이 아니다. 그것은 워프 실행 모델(Warp Execution Model), 메모리 계층 구조(Memory Hierarchy), **코알레싱(Coalescing)**이라는 GPU의 하드웨어적 특성을 완벽하게 이해하고 설계된 정교한 엔진이다.

  • 해시 테이블과 선형 조사법은 포인터 추적 비용을 제거하고 O(1) 접근을 보장하여 랜덤 액세스 지연을 최소화했다.
  • SoA 레이아웃은 메모리 대역폭을 낭비 없이 사용하여 GPU의 연산 처리량(Throughput)을 한계까지 끌어올렸다.
  • 원자적 연산과 락-프리 알고리즘은 수만 개의 스레드가 멈춤 없이 동시에 맵을 구축할 수 있는 병렬성을 확보했다.

이러한 GPU 친화적(GPU-friendly) 데이터 구조의 채택이야말로, CPU 기반의 기존 매핑 기술들이 도달하지 못했던 실시간 고해상도 매핑의 영역을 NvBlox가 개척할 수 있었던 근본적인 원동력이다. 이어지는 절에서는 이 데이터 구조 위에서 실제로 레이어들이 어떻게 적층되고 관리되는지, ‘레이어케이크(LayerCake)’ 아키텍처에 대해 다룰 것이다.

7. 참고 자료

  1. Why are oct trees so much more common than hash tables?, https://computergraphics.stackexchange.com/questions/8364/why-are-oct-trees-so-much-more-common-than-hash-tables
  2. Voxblox: Incremental 3D Euclidean Signed Distance Fields for on-board MAV planning, https://www.researchgate.net/publication/321810704_Voxblox_Incremental_3D_Euclidean_Signed_Distance_Fields_for_on-board_MAV_planning
  3. Resolution Where It Counts: Hash-based GPU-Accelerated 3D Reconstruction via Variance-Adaptive Voxel Grids - arXiv, https://arxiv.org/html/2511.21459
  4. nvblox: GPU-Accelerated Incremental Signed Distance Field Mapping | Request PDF, https://www.researchgate.net/publication/382991572_nvblox_GPU-Accelerated_Incremental_Signed_Distance_Field_Mapping
  5. nvblox: GPU-Accelerated Incremental Signed Distance Field Mapping - arXiv, https://arxiv.org/html/2311.00626v2
  6. coVoxSLAM: GPU accelerated globally consistent dense SLAM - arXiv, https://arxiv.org/html/2410.21149v1
  7. Real-Time Metric-Semantic Mapping for Autonomous Navigation in Outdoor Environments - UCL Discovery, https://discovery.ucl.ac.uk/10194629/1/tase2024_metric_semantic_mapping_navigation.pdf
  8. Real-Time Metric-Semantic Mapping for Autonomous Navigation in Outdoor Environments, https://arxiv.org/html/2412.00291v1
  9. Linear probing - Wikipedia, https://en.wikipedia.org/wiki/Linear_probing
  10. Maximizing Performance with Massively Parallel Hash Maps on GPUs - NVIDIA Developer, https://developer.nvidia.com/blog/maximizing-performance-with-massively-parallel-hash-maps-on-gpus/
  11. A Simple GPU Hash Table - Nosferalatu, https://nosferalatu.com/SimpleGPUHashTable.html
  12. Is Linear Probing Really that Bad of a Solution for Open-Addressing? : r/computerscience, https://www.reddit.com/r/computerscience/comments/1kb3bea/is_linear_probing_really_that_bad_of_a_solution/
  13. (PDF) Faster-LIO: Lightweight Tightly Coupled Lidar-Inertial Odometry Using Parallel Sparse Incremental Voxels - ResearchGate, https://www.researchgate.net/publication/359662313_Faster-LIO_Lightweight_Tightly_Coupled_Lidar-Inertial_Odometry_Using_Parallel_Sparse_Incremental_Voxels
  14. Nvblox quickstart example crashing - Isaac ROS - NVIDIA Developer Forums, https://forums.developer.nvidia.com/t/nvblox-quickstart-example-crashing/333188
  15. SoA in webgpu - Reddit, https://www.reddit.com/r/webgpu/comments/1fqcysi/soa_in_webgpu/
  16. coVoxSLAM: GPU Accelerated Globally Consistent Dense SLAM | Request PDF, https://www.researchgate.net/publication/395224211_coVoxSLAM_GPU_Accelerated_Globally_Consistent_Dense_SLAM
  17. Technical Details — isaac_ros_docs documentation - NVIDIA Isaac ROS, https://nvidia-isaac-ros.github.io/v/release-3.1/concepts/scene_reconstruction/nvblox/technical_details.html
  18. [Thrust] is there a managed_vector? With Unified Memory do we still only have device_vector? [Cuda Thrust Managed Vectors] - NVIDIA Developer Forums, https://forums.developer.nvidia.com/t/thrust-is-there-a-managed-vector-with-unified-memory-do-we-still-only-have-device-vector-cuda-thrust-managed-vectors/47249